package com.zhupf.part7;

import java.util.List;

/**
 * @author zhupf
 * @date 2023年11月10日 10:50
 * @Description
 */
public class IsPalindrome {

    public static void main(String[] args) {
//        ListNode head = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(3,new ListNode(2,new ListNode(1) )))));
        ListNode head = new ListNode(1,new ListNode(2));
        System.out.println(isPalindrome2(head));
    }

    public static boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        int len = 0;
        ListNode h = head;
        while (h != null){
            len++;
            h = h.next;
        }
        int mid = len / 2;
        int i = 1;
        h = head;
        ListNode t = null;
        ListNode midNode = null;
        while (h != null){
            ListNode tmp = h.next;
            if(i == mid){
                midNode = h;
            }
            if(i > mid){
                h.next = t;
                t = h;
            }
            h = tmp;
            i ++;
        }
        boolean result = true;
        h = head;
        ListNode t1 = t;
        for (i = 1 ; i <= mid ;  i ++){
            if(h.val != t1.val ){
                result = false;
                break;
            }
            h = h.next;
            t1 = t1.next;
        }
        t1 = t;
        t = null;
        while (t1 != null){
            ListNode tmp = t1.next;
            t1.next = t;
            t = t1;
            t1 = tmp;
        }
        midNode.next = t;
        return result;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }



    public static boolean isPalindrome2 (ListNode head) {
        if (head == null) {
            return true;
        }
        boolean result = true;
        ListNode preNode = head;
        ListNode n1 = head;
        while (n1.next != null && n1.next.next != null){
            preNode = preNode.next;
            n1 = n1.next.next;
        }
        ListNode secondNode = reserveNode(preNode.next);
        ListNode p1 = head;
        ListNode p2 = secondNode;
        while (result && p2 != null ){
            if(p1.val != p2.val){
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        preNode.next = reserveNode(secondNode);
        return result;
    }

    public static ListNode reserveNode(ListNode head){
        ListNode result = null;
        ListNode p = head;
        while (p != null){
            ListNode t = p.next;
            p.next = result;
            result  = p;
            p = t;
        }
        return result;
    }



}
